Clickthrough Log Analysis by Collaborative Ranking.
Analyzing clickthrough log data is important for improving search performance as well as understanding user behaviors. In this paper, we propose a novel collaborative ranking model to tackle two difficulties in analyzing clickthrough log. First, previous studies have shown that users tend to click topranked results even they are less relevant. Therefore, we use pairwise ranking relation to avoid the position bias in clicks. Second, since click data are extremely sparse with respect to each query or user, we construct a collaboration model to eliminate the sparseness problem. We also find that the proposed model and previous popular used click-based models address different aspects of clickthrough log data. We further propose a hybrid model that can achieve significant improvement compared to the baselines on a large-scale real world dataset.
Learning to rank audience for behavioral targeting.

Learning with click graph for query intent classification.

Proceedings of the 3rd ACM SIGKDD Workshop on Data Mining and Audience Intelligence for Advertising



Exploiting term relationship to boost text classification.

Product query classification.

Context%2Daware query classification.
Abstract. With more and more commercial activities moving onto the Internet, people tend to purchase what they need through Internet or conduct some online research before the actual transactions happen. For many Web users, their online commercial activities start from submitting a search query to search engines. Just like the common Web search queries, the queries with commercial intention are usually very short. Recognizing the queries with commercial intention against the common queries will help search engines provide proper search results and advertisements, help Web users obtain the right information they desire and help the advertisers benefit from the potential transactions. However, the intentions behind a query vary a lot for users with different background and interest. The intentions can even be different for the same user, when the query is issued in different contexts. In this paper, we present a new algorithm framework based on skip-chain conditional random field (SCCRF) for automatically classifying Web queries according to context-based online commercial intention. We analyze our algorithm performance both theoretically and empirically. Extensive experiments on several real search engine log datasets show that our algorithm can improve more than 10 % on F1 score than previous algorithms on commercial intention detection. 1
Mining common topics from multiple asynchronous text streams.

Text Categorization.
The automated categorization (or classification) of texts into predefined categories has witnessed a booming interest in the last ten years, due to the increased availability of documents in digital form and the ensuing need to organize them. In the research community the dominant approach to this problem is based on machine learning techniques: a general inductive process automatically builds a classifier by learning, from a set of preclassified documents, the characteristics of the categories. The advantages of this approach over the knowledge engineering approach (consisting in the manual definition of a classifier by domain experts) are a very good effectiveness, considerable savings in terms of expert labor power, and straightforward portability to different domains. This survey discusses the main approaches to text categorization that fall within the machine learning paradigm. We will discuss in detail issues pertaining to three different problems, namely document representation, classifier construction, and classifier evaluation.
Text Categorization.
The automated categorization (or classification) of texts into predefined categories has witnessed a booming interest in the last ten years, due to the increased availability of documents in digital form and the ensuing need to organize them. In the research community the dominant approach to this problem is based on machine learning techniques: a general inductive process automatically builds a classifier by learning, from a set of preclassified documents, the characteristics of the categories. The advantages of this approach over the knowledge engineering approach (consisting in the manual definition of a classifier by domain experts) are a very good effectiveness, considerable savings in terms of expert labor power, and straightforward portability to different domains. This survey discusses the main approaches to text categorization that fall within the machine learning paradigm. We will discuss in detail issues pertaining to three different problems, namely document representation, classifier construction, and classifier evaluation.
Transferring Localization Models across Space.
Machine learning approaches to indoor WiFi localization involve an offline phase and an online phase. In the offline phase, data are collected from an environment to build a localization model, which will be applied to new data collected in the online phase for location estimation. However, collecting the labeled data across an entire building would be too time consuming. In this paper, we present a novel approach to transferring the learning model trained on data from one area of a building to another. We learn a mapping function between the signal space and the location space by solving an optimization problem based on manifold learning techniques. A low-dimensional manifold is shared between data collected in different areas in an environment as a bridge to propagate the knowledge across the whole environment. With the help of the transferred knowledge, we can significantly reduce the amount of labeled data which are required for building the localization model. We test the effectiveness of our proposed solution in a real indoor WiFi environment.
Text Summarization.
We investigate one technique to produce a summary of an original text without requiring its full semantic interpretation, but instead relying on a model of the topic progression in the text derived from lexical chains. We present a new algorithm to compute lexical chains in a text, merging several robust knowledge sources: the WordNet thesaurus, a part-of-speech tagger and shallow parser for the ldentification of nominal groups, and a segmentation algorithm derived from (Hearst, 1994) Summarization proceeds in three steps: the original text m first segmented, lexical chains are constructed, strong chains are identified and significant sentences are extracted from the text. We present in this paper empirical results on the identification of strong chain and of significant sentences.
Transferring Localization Models across Space.
Machine learning approaches to indoor WiFi localization involve an offline phase and an online phase. In the offline phase, data are collected from an environment to build a localization model, which will be applied to new data collected in the online phase for location estimation. However, collecting the labeled data across an entire building would be too time consuming. In this paper, we present a novel approach to transferring the learning model trained on data from one area of a building to another. We learn a mapping function between the signal space and the location space by solving an optimization problem based on manifold learning techniques. A low-dimensional manifold is shared between data collected in different areas in an environment as a bridge to propagate the knowledge across the whole environment. With the help of the transferred knowledge, we can significantly reduce the amount of labeled data which are required for building the localization model. We test the effectiveness of our proposed solution in a real indoor WiFi environment.


Personal name classification in web queries.

Report on the second KDD workshop on data mining for advertising.

Activity recognition via user%2Dtrace segmentation.
A major issue of activity recognition in sensor networks is automatically recognizing a user’s highlevel goals accurately from low-level sensor data. Traditionally, solutions to this problem involve the use of a location-based sensor model that predicts the physical locations of a user from the sensor data. This sensor model is often trained offline, incurring a large amount of calibration effort. In this article, we address the problem using a goal-based segmentation approach, in which we automatically segment the low-level user traces that are obtained cheaply by collecting the signal sequences as a user moves in wireless environments. From the traces we discover primitive signal segments that can be used for building a probabilistic activity model to recognize goals directly. A major advantage of our algorithm is that it can reduce a significant amount of human effort in calibrating the sensor data while still achieving comparable recognition accuracy. We present our theoretical framework for activity recognition, and demonstrate the effectiveness of our new approach using the data collected in an indoor wireless environment. 
Mining Web Query Hierarchies from Clickthrough Data.
In this paper, we propose to mine query hierarchies from clickthrough data, which is within the larger area of automatic acquisition of knowledge from the Web. When a user submits a query to a search engine and clicks on the returned Web pages, the user’s understanding of the query as well as its relation to the Web pages is encoded in the clickthrough data. With millions of queries being submitted to search engines every day, it is both important and beneficial to mine the knowledge hidden in the queries and their intended Web pages. We can use this information in various ways, such as providing query suggestions and organizing the queries. In this paper, we plan to exploit the knowledge hidden in clickthrough logs by constructing query hierarchies, which can reflect the relationship among queries. Our proposed method consists of two stages: generating candidate queries and determining “generalization/specialization” relations between these queries in a hierarchy. We test our method on some labeled data sets and illustrate the effectiveness of our proposed solution empirically.
Understanding Topic Influence Based on Module Network.

Feature selection in a kernel space.
We address the problem of feature selection in a kernel space to select the most discriminative and informative features for classification and data analysis. This is a difficult problem because the dimension of a kernel space may be infinite. In the past, little work has been done on feature selection in a kernel space. To solve this problem, we derive a basis set in the kernel space as a first step for feature selection. Using the basis set, we then extend the margin-based feature selection algorithms that are proven effective even when many features are dependent. The selected features form a subspace of the kernel space, in which different state-of-the-art classification algorithms can be applied for classification. We conduct extensive experiments over real and simulated data to compare our proposed method with four baseline algorithms. Both theoretical analysis and experimental results validate the effectiveness of our proposed method.
Detect and Track Latent Factors with Online Nonnegative Matrix Factorization.

Document Summarization Using Conditional Random Fields.
Many methods, including supervised and unsupervised algorithms, have been developed for extractive document summarization. Most supervised methods consider the summarization task as a twoclass classification problem and classify each sentence individually without leveraging the relationship among sentences. The unsupervised methods use heuristic rules to select the most informative sentences into a summary directly, which are hard to generalize. In this paper, we present a Conditional Random Fields (CRF) based framework to keep the merits of the above two kinds of approaches while avoiding their disadvantages. What is more, the proposed framework can take the outcomes of previous methods as features and seamlessly integrate them. The key idea of our approach is to treat the summarization task as a sequence labeling problem. In this view, each document is a sequence of sentences and the summarization procedure labels the sentences by 1 and 0. The label of a sentence depends on the assignment of labels of others. We compared our proposed approach with eight existing methods on an open benchmark data set. The results show that our approach can improve the performance by more than 7.1 % and 12.1 % over the best supervised baseline and unsupervised baseline respectively in terms of two popular metrics F1 and ROUGE-2. Detailed analysis of the improvement is presented as well. 1
Domain%2Dconstrained semi%2Dsupervised mining of tracking models in sensor networks.

Noise reduction through summarization for Web%2Dpage classification.

Noise reduction through summarization for Web%2Dpage classification.

Data mining and audience intelligence for advertising.

Text classification improved through multigram models.

Text Classification Improved through Automatically Extracted Sequences.

Latent Friend Mining from Blog Data.
The rapid growth of blog (also known as “weblog”) data provides a rich resource for social community mining. In this paper, we put forward a novel research problem of mining the latent friends of bloggers based on the contents of their blog entries. Latent friends are defined in this paper as people who share the similar topic distribution in their blogs. These people may not actually know each other, but they have the interest and potential to find each other out. Three approaches are designed for latent friend detection. The first one, called cosine similarity-based method, determines the similarity between bloggers by calculating the cosine similarity between the contents of the blogs. The second approach, known as topic-based method, is based on the discovery of latent topics using a latent topic model and then calculating the similarity at the topic level. The third one is two-level similarity-based, which is conducted in two stages. In the first stage, an existing topic hierarchy is exploited to build a topic distribution for a blogger. Then, in the second stage, a detailed similarity comparison is conducted for bloggers that are close in interest to each other which are discovered in the first stage. Our experimental results show that both the topic-based and two-level similarity-based methods work well, and the last approach performs much better than the first two. In this paper, we give a detailed analysis of the advantages and disadvantages of different approaches. 1.
Adding Semantics to Email Clustering.

Building bridges for web query classification.
Web query classification (QC) aims to classify Web users’ queries, which are often short and ambiguous, into a set of target categories. QC has many applications including page ranking in Web search, targeted advertisement in response to queries, and personalization. In this paper, we present a novel approach for QC that outperforms the winning solution of the ACM KDDCUP 2005 competition, whose objective is to classify 800,000 real user queries. In our approach, we first build a bridging classifier on an intermediate taxonomy in an offline mode. This classifier is then used in an online mode to map user queries to the target categories via the above intermediate taxonomy. A major innovation is that by leveraging the similarity distribution over the intermediate taxonomy, we do not need to retrain a new classifier for each new set of target categories, and therefore the bridging classifier needs to be trained only once. In addition, we introduce category selection as a new method for narrowing down the scope of the intermediate taxonomy based on which we classify the queries. Category selection can improve both efficiency and effectiveness of the online classification. By combining our algorithm with the winning solution of KDDCUP 2005, we made an improvement by 9.7 % and 3.8 % in terms of precision and F1 respectively compared with the best results of KDDCUP 2005.
Thread detection in dynamic text message streams.

CWS a comparative web search system.

A comparison of implicit and explicit links for web page classification.
It is well known that Web-page classification can be enhanced by using hyperlinks that provide linkages between Web pages. However, in the Web space, hyperlinks are usually sparse, noisy and thus in many situations can only provide limited help in classification. In this paper, we extend the concept of linkages from explicit hyperlinks to implicit links built between Web pages. By observing that people who search the Web with the same queries often click on di#erent, but related documents together, we draw implicit links between Web pages that are clicked after the same queries. Those pages are implicitly linked. We provide an approach for automatically building the implicit links between Web pages using Web query logs, together with a thorough comparison between the uses of implicit and explicit links in Web page classification. Our experimental results on a large dataset confirm that the use of the implicit links is better than using explicit links in classification performance, with an increase of more than 10.5% in terms of the Macro-F1 measurement.
Mining clickthrough data for collaborative web search.

Query enrichment for web%2Dquery classification.
Web search queries are typically short and ambiguous. To classify these queries into certain target categories is a difficult but important problem. In this paper, we present a new technique called query enrichment, which takes a short query and maps it to the intermediate objects. Based on the collected intermediate objects, the query is then mapped to the target categories. To build the necessary mapping functions, we use an ensemble of search engines to produce an enrichment of the queries. Our technique was applied to ACM Knowledge-discovery and data mining competition (ACM KDDCUP) in 2005, where we won the championship on all three evaluation metrics (precision, F1 measure, which combines precision and recall together, and creativity, which is judged by the organizers) among a total of 33 teams worldwide. In this paper, we show that, despite the difficulty in an abundance of ambiguous queries and a lack of training data, our query-enrichment technique can solve the problem satisfactorily through a two-phase classification framework. We present a detailed description of our algorithm and experimental evaluation. Our best result of F1 and precision are 42.4 % and 44.4%, respectively, which are 9.6%
Activity Recognition through Goal%2DBased Segmentation.
Amajor issue in activity recognition in a sensor network  is how to automatically segment the low-level signal sequences  in order to optimize the probabilistic recognition  models for goals and activities. Past efforts have relied  on segmenting the signal sequences by hand, which  is both time-consuming and error-prone. In our view,  segments should correspond to atomic human activities  that enable a goal-recognizer to operate optimally; the  two are intimately related. In this paper, we present a  novel method for building probabilistic activity models  at the same time as we segment signal sequences  into motion patterns. We model each motion pattern as  a linear dynamic model and the transitions between motion  patterns as a Markov process conditioned on goals.
Web%2Dpage summarization using clickthrough data.
Most previous Web-page summarization methods treat a Web page as plain text. However, such methods fail to uncover the full knowledge associated with a Web page to build a high-quality summary, because the Web contains many hidden relationships that are not used in these methods. Uncovering the inherent knowledge is important to building good Web-page summarizers. In this paper, we extract the extra knowledge from the clickthrough data of a Web search engine to improve Web-page summarization. We first analyze the feasibility to utilize clickthrough data in text summarization, and then propose two adapted summarization methods that take advantage of the relationships discovered from the clickthrough data. For those pages not covered by the clickthrough data, we put forward a thematic lexicon approach to generate implicit knowledge for them. Our methods are evaluated on a relatively small dataset consisting of manually annotated pages as well as a large dataset that is crawled from the Open Directory Project website. The experimental results indicate that significant improvements can be achieved through our proposed summarizer as compared with summarizers without using the clickthrough data. Categories and Subject Descriptors H.4 [Information Systems Applications]: Miscellaneous; I.5.4 [Pattern Recognition]: Applications—Text processing
Q2C%40UST our winning solution to query classification in KDDCUP 2005.

Web page clustering enhanced by summarization.

IRC An Iterative Reinforcement Categorization Algorithm for Interrelated Web Objects.
Most existing categorization algorithms deal with homogeneous Web data objects, and consider interrelated objects as additional features when taking the interrelationships with other types of objects into account. However, focusing on any single aspects of these interrelationships and objects will not fully reveal their true categories. In this paper, we propose a novel categorization algorithm, the Iterative Reinforcement Categorization algorithm (IRC), to exploit the full interrelationships between the heterogeneous objects on the Web. IRC attempts to classify the interrelated Web objects by iterative reinforcement between individual classification results of different types via the interrelationships. Experiments on a clickthrough log dataset from MSN search engine show that, with the F1 measures, IRC achieves a 26.4 % improvement over a pure content-based classification method, a 21% improvement over a query metadata-based method, and a 16.4 % improvement over a virtual document-based method. Furthermore, our experiments show that IRC converges rapidly. 1.
Web%2Dpage classification through summarization.

